package increasingBST;

import java.util.*;

public class Solution {
    public class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
  }
    public class ListNode {
        int val;
        ListNode next;
      ListNode() {}
      ListNode(int val) { this.val = val; }
      ListNode(int val, ListNode next) { this.val = val; this.next = next; }
  }
    public TreeNode increasingBST(TreeNode root) {
        //
        TreeNode dummy = new TreeNode();
        TreeNode p = dummy;
        Stack<TreeNode> stack = new Stack<>();
        while (root!=null || !stack.isEmpty()) {
            while (root!=null) {
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            p.right = root;
            p.left = null;
            p = p.right;
            root = root.right;
        }
        p.left = null;
        return dummy.right;
    }
    // 反转链表
    public ListNode reverseList(ListNode head) {
        if(head == null || head.next == null) {
            return head;
        }
        ListNode newHead = reverseList(head);
        head.next.next = head;
        head.next = null;
        return newHead;
    }
    public int[] reverseBookList(ListNode head) {
        List<Integer> list = new ArrayList<>();
        dfs(head,list);
        int[] ans = new int[list.size()];
        for (int i = 0; i < list.size(); i++) {
            ans[i] = list.get(i);
        }
        return ans;
    }
    private void dfs(ListNode cur,List<Integer> list) {
        if(cur == null) return;
        dfs(cur.next,list);
        list.add(cur.val);
    }
    class CQueue {
        Stack<Integer> inStack;
        Stack<Integer> outStack;
        public CQueue() {
            inStack = new Stack<>();
            outStack = new Stack<>();
        }

        public void appendTail(int value) {
            inStack.push(value);
        }

        public int deleteHead() {
            if(outStack.isEmpty()) {
                in2out();
            }
            return outStack.isEmpty()?outStack.pop():-1;
        }
        private void in2out() {
            while (!inStack.isEmpty()) {
                outStack.push(inStack.pop());
            }
        }
    }
    class TripleInOne {
        int[] arr;
        int[] size = new int[3];
        int stackSize;
        public TripleInOne(int stackSize) {
            this.stackSize = stackSize;
            arr = new int[stackSize*3];
        }

        public void push(int stackNum, int value) {
            // 添加元素
            if(size[stackNum]<stackSize) {
                arr[stackNum*stackSize + size[stackNum]] = value;
                size[stackNum]++;
            }
        }

        public int pop(int stackNum) {
            // 弹出最后一个元素
            if ( isEmpty(stackNum) ) {
                return -1;
            }
            return arr[stackNum*stackSize+(--size[stackNum])];
        }

        public int peek(int stackNum) {
            if( isEmpty(stackNum) ) {
                return -1;
            }
            return arr[stackNum*stackSize+size[stackNum]-1];
        }
        public boolean isEmpty(int stackNum) {
            return size[stackNum] == 0;
        }
    }
    class MinStack {

        /** initialize your data structure here. */
        Stack<Integer> stack = new Stack<>();
        Stack<Integer> minStack = new Stack<>();
        public MinStack() {
            minStack.push(Integer.MAX_VALUE);
        }

        public void push(int x) {
            stack.push(x);
            minStack.push(Math.min(minStack.peek(),x));
        }

        public void pop() {
            stack.pop();
            minStack.pop();
        }

        public int top() {
            return stack.peek();
        }

        public int getMin() {
            return minStack.peek();
        }
    }
    class MyQueue {

        /** Initialize your data structure here. */
        Stack<Integer> inStack;
        Stack<Integer> outStack;
        public MyQueue() {
            inStack = new Stack<>();
            outStack = new Stack<>();
        }

        /** Push element x to the back of queue. */
        public void push(int x) {
            inStack.push(x);
        }

        /** Removes the element from in front of queue and returns that element. */
        public int pop() {
            if(outStack.isEmpty()) {
                in2Out();
            }
            return outStack.isEmpty()?-1:outStack.pop();
        }

        /** Get the front element. */
        public int peek() {
            if(outStack.isEmpty()) {
                in2Out();
            }
            return outStack.isEmpty()?-1:outStack.peek();
        }

        /** Returns whether the queue is empty. */
        public boolean empty() {
            if(outStack.isEmpty()) {
                in2Out();
            }
            return outStack.isEmpty();
        }
        private void in2Out(){
            while (!inStack.isEmpty()) {
                outStack.push(inStack.pop());
            }
        }
    }
    public TreeNode convertBiNode(TreeNode root) {
        // 深度优先搜索
        TreeNode dummy = new TreeNode();
        TreeNode p = dummy;
        Stack<TreeNode> stack = new Stack<>();
        while (root!=null || !stack.isEmpty()) {
            while (root!=null) {
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            p.right = root;
            p.left = null;
            p = p.right;
            root = root.right;
        }
        p.left = null;
        return dummy.right;
    }
    class MyStack {
        Queue<Integer> queue1 = new ArrayDeque<>();
        Queue<Integer> queue2 = new ArrayDeque<>();
        public MyStack() {

        }

        public void push(int x) {
            queue2.add(x);
            while (!queue1.isEmpty()) {
                queue2.add(queue1.poll());
            }
            Queue<Integer> tmp = queue1;
            queue1 = queue2;
            queue2 = tmp;
        }

        public int pop() {
            return queue1.poll();
        }

        public int top() {
            return queue1.peek();
        }

        public boolean empty() {
            return queue1.isEmpty();
        }
    }
    public int firstUniqChar(String s) {
        Queue<Pair> queue = new ArrayDeque<>();
        Set<Character> set = new HashSet<>();
        Set<Character> set1 = new HashSet<>();
        int n = s.length();
        for (int i = 0; i < n; i++) {
            char ch = s.charAt(i);
            if(set.add(ch)) {
               queue.offer(new Pair(ch,i));
            } else {
                set1.add(ch);
                while (!queue.isEmpty() && set1.contains(queue.peek().ch)) {
                    queue.poll();
                }
            }
        }
        return queue.isEmpty()?-1:queue.poll().pos;
    }
    class Pair {
        char ch;
        int pos;
        Pair(char ch, int pos) {
            this.ch = ch;
            this.pos = pos;
        }
    }
    class RecentCounter {
        Queue<Integer> queue = new ArrayDeque<>();
        public RecentCounter() {

        }

        public int ping(int t) {
            queue.offer(t);
            while (queue.peek() < t-3000) {
                queue.poll();
            }
            return queue.size();
        }
    }
    class AnimalShelf {
        class Pair {
            int time;
            int[] data;
            Pair(int time,int[] data){
                this.time = time;
                this.data = data;
            }
        }
        Queue<Pair> cat = new ArrayDeque<>();
        Queue<Pair> dog = new ArrayDeque<>();
        int t = 0;
        public AnimalShelf() {

        }
        public void enqueue(int[] animal) {
            if(animal[1] == 0) {
                cat.offer(new Pair(t,animal));
            } else {
                dog.offer(new Pair(t,animal));
            }
            t++;
        }
        public int[] dequeueAny() {
            if(cat.isEmpty()&&dog.isEmpty())return new int[]{-1,-1};
            if(cat.isEmpty()) return dog.poll().data;
            if(dog.isEmpty()) return cat.poll().data;
            if(dog.peek().time>cat.peek().time) return cat.poll().data;
            return dog.poll().data;
        }
        public int[] dequeueDog() {
            if(dog.isEmpty()) {
                return new int[]{-1,-1};
            }
            return dog.poll().data;
        }

        public int[] dequeueCat() {
            if(cat.isEmpty()){
                return new int[]{-1,-1};
            }
            return cat.poll().data;
        }
    }
}
